package algorithm.backtracing;

import util.GsonUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 77. Combinations
 * leetcode : https://leetcode.com/problems/combinations/
 * Difficulty : Medium
 *
 * 给两个数字 n 和 k。
 * 返回数字从 1~n 的 包含k个数字的所有可能组合
 *
 * 这就是排列组合里的，组合问题
 * @Author Antony
 * @Since 2018/11/16 15:29
 */
public class Combinations {

    public static void main(String[] args) {
        System.out.println(GsonUtil.toJson(combine(4,4)));
    }

    /**
     * leetcode 22ms - beats 64.50%
     * @param n
     * @param k
     * @return
     */
    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        if(n<k){
            return result;
        }
        backtrack_BFS(result, new ArrayList<>(), 1, k, n);
        return result;
    }

    private static void backtrack_BFS(List<List<Integer>> result, List<Integer> tmpList, int currNum, int remainNum, int numSize){
        if(remainNum == 0){
            result.add(new ArrayList<>(tmpList));
        }else{
            for(int i=currNum; i<=numSize; i++){
                tmpList.add(i);
                backtrack_BFS(result, tmpList, i+1, remainNum-1, numSize);
                tmpList.remove(tmpList.size()-1);
            }
        }
    }
}
